package offerbook;


import baseclass.e_tree.Code04_SerializeAndReconstructTree;
import utils.TreeNode;

/**
 * 问题2：输入两个二叉树A、B，判断B是不是A的子树
 * 更多序列化方式见
 *{@link Code04_SerializeAndReconstructTree}
 * @date 2020/3/9 13:43
 */
public class Code18_IsSubTree {
    /**
     * 方式2：先遍历A，找到A和B一样后，开始判断
     */
    public boolean hasSubTree2(TreeNode root1, TreeNode  root2) {
        if(root1 == null || root2 == null) return false;
        boolean res = false;
        //if get the same label,go to judge
        if(root1.val == root2.val){
            res = process(root1,root2);
        }
        if(!res)
            res = hasSubTree2(root1.left,root2);
        if(!res)
            res = hasSubTree2(root1.right,root2);
        return res;
    }
    public boolean process(TreeNode  root1, TreeNode  root2) {
        //must have the same
        if(root1 == null && root2 == null) return true;
        if(root1 == null || root2 == null) return false;

        //assert all the root is not null
        if(root1.val != root2.val){
            return false;
        }
        return process(root1.left,root2.left)
                && process(root1.right,root2.right);
    }
    /**
     * 方法3，采用序列化的方式.
     * 更多序列化方式见
     * {@link Code04_SerializeAndReconstructTree}
     */
    public static boolean hasSubTree3(TreeNode  root1, TreeNode  root2) {
        return serialTreeByPre(root1).contains(serialTreeByPre(root2));
    }

    /**
     * 先序遍历的方式序列化一颗二叉树 ，以_结尾，空节点以null表示
     * 注意节点还要用另外任意符号如@包裹，不然会出错。见笔记说明
     */
    private static String serialTreeByPre(TreeNode  head) {
        String res;
        if (head == null) {
            return "#_";
        }
        res = "@" + head.val + "@_";
        res += serialTreeByPre(head.left);
        res += serialTreeByPre(head.right);
        return res;
    }
}
